
#include "sequential.h"
#include<math.h>

SequentialSearch::SequentialSearch(int n, int d)
{
    number_points = n;
    number_dimensions = d;
}

SequentialSearch::~SequentialSearch()
{}

//return ids for a given point location
vector<int> SequentialSearch::FindOne(double **data, double **p)
{
    bool equal;
    vector<int> ret_points;
    int index;
    for(int i = 0; i < number_points; i++)
    {
      equal = true;
      index = i*number_dimensions;
      for(int j = 0; j < number_dimensions; j++)
      {
        //if all dimensions are equal, the points are equal
        if(data[index][j] != p[i][j])
            equal = false;
      }
      if(equal == true)
      {
          //add point id to return list
          ret_points.push_back(i);
      }
    }
    return ret_points;
}

//return anything in the range between low_range, high_range
vector<int> SequentialSearch::Range(double ** data, double * low_range, double * high_range)
{
    bool inrange;
    vector<int> ret_points;
    int index;
    for(int i = 0; i < number_points; i++)
    {
      inrange = true;
      index = i*number_dimensions;
      for(int j = 0; j < number_dimensions; j++)
      {
        //if > low range and < high range, it's in range
        if(data[index][j] < low_range[j] || data[index][j]  > high_range[j])
            inrange = false;
      }
      if(inrange == true)
      {
          //add point id to return list
          ret_points.push_back(i);
      }
    }
    return ret_points;
}


//keep an ordered list from smallest to largest of neighbors
vector<int> SequentialSearch::KNN(double **data, double ** p, int num)
{
    vector<int> knn;            //list of knn indices
    vector<double> knn_dist;    //distance of those knn indices
    double current_dist;
    double sum;
    int k;
    int index;
    for(int i = 0; i < number_points; i++)
    {
        //calculate distance
        sum = 0;
        index = i*number_dimensions;
        for(int j = 0; j < number_dimensions; j++)
        {
            sum += pow(data[index][j] - p[i][j], 2);
        }
        current_dist = sqrt(sum);
        if(!knn_dist.empty())
        {   //if it needs to be inserted before last element
            if(current_dist < knn_dist.back())
            {
                //finding the right insert spot
                for(k=knn_dist.size()-1; current_dist < knn_dist.at(k) && k>=0; k--)
                {}
                //if k=0 we need to know if we insert at 0 or 1
                if(k==0 && current_dist < knn_dist.at(0))
                {
                    knn.insert(knn.begin(), i);
                    knn_dist.insert(knn_dist.begin(), current_dist);
                }
                else
                {
                    //insert at one greater than k
                    knn.insert(knn.begin() + k + 1, i);
                    knn_dist.insert(knn_dist.begin() + k + 1, current_dist);
                }
                //if we now have num+1 neighbors
                if(knn.size() > num)
                {
                    knn.pop_back();
                    knn_dist.pop_back();
                }
            }
            else
            {   //if we're still less than how many neighbors we want,
                //we can just add it to the end
                if(knn.size() < num)
                {
                    knn.push_back(i);
                    knn_dist.push_back(current_dist);
                }
            }
        }
        else
        {   //add to empty list
            knn.push_back(i);
            knn_dist.push_back(current_dist);
        }
    }
    return knn;
}

